package com.zy.stack;

import java.util.Stack;

/**
 * Created by zhaoyi on 2019/7/18
 * desc   每日温度 应该附带上我画的草图
 * https://leetcode-cn.com/explore/learn/card/queue-stack/218/stack-last-in-first-out-data-structure/879/
 */
public class StackdailyTemperatures {

    //[73, 74, 75, 71, 69, 72, 76, 73]
    public int[] dailyTemperatures(int[] T) {
        //用来存放还没找到比他大的值得index
        Stack<Integer> stackIndex = new Stack<>();
        //存值
        Stack<Integer> stackValue = new Stack<>();

        for (int i = 0; i < T.length; i++) {
            if (stackValue.isEmpty() || stackValue.peek() >= T[i]) {
                stackValue.push(T[i]);
                stackIndex.push(i);
            } else {
                Integer top = stackValue.peek();
                Integer index = stackIndex.peek();
                while (top < T[i]) {
                    stackValue.pop();
                    stackIndex.pop();
                    T[index] = i - index;
                    if (stackValue.isEmpty()) {
                        break;
                    }
                    top = stackValue.peek();
                    index = stackIndex.peek();
                }
                stackValue.push(T[i]);
                stackIndex.push(i);
            }
        }
        while (!stackIndex.isEmpty()) {
            Integer index = stackIndex.pop();
            T[index] = 0;
        }
        return T;
    }

}
